package com.查找算法;


class Solution5 {
    //法一:暴力遍历
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == target) return true;
            }

        }
        return false;
    }
    //法二：充分利用题目条件，利用类似二叉排序数的性质来解题。
    public boolean findNumberIn2DArray2(int[][] matrix, int target){
        int i=matrix.length-1,j=0;
        while(i>=0&& j<matrix[0].length){
            if(matrix[i][j]>target) i--;
            else if(matrix[i][j]<target) j++;
            else return true;
        }
        return false;
    }
}

public class 剑指Offer04二维数组中的查找 {
    public static void main(String[] args) {
        int[][] mat = new int[][]{{1, 4, 7, 11, 15},
                {2, 5, 8, 12, 19},
                {3, 6, 9, 16, 22},
                {10, 13, 14, 17, 24},
                {18, 21, 23, 26, 30}};
        Solution5 s=new Solution5();
        System.out.println(s.findNumberIn2DArray(mat,100));

    }
}
